package com.since.algorithm.search;

import java.util.Arrays;

/**
 * Created by Sincerity on 2020/5/16.
 * 描述： 斐波那契查找
 * <a>斐波那契数列{1,1,2,3,5,8,13,21,34,55.........} 并且相邻二个数的商无线接近0.618黄金分割线</a>
 * F(i)=F(i-2)+F(i-1)  mid =Left+F(block-1)-1
 * 假设有集合 e0=2, e1=3, e2=7, e3=14, e4=22, e5=33, e6=55, e7=75, e8=89, e9=123
 * 查找元素14的过程已知：
 * 元素数量size = 10；
 * 下标区间 [left, right] 为left = 0、right = 9。则初始化的斐波那契数列为 Fib={1,1,2,3,5,8,13} ，即斐波那契数列最后一位要比size - 1大
 * 此时查找第一步为： 此时刚初始化完，斐波那契数列最后一个区间为第6个区间，即区间(8, 13)；
 * 第8个数字为当前黄金分割点，则第8个数字下标为下标7，检测的数字为 e7=75 ；以8分割数组后，左区间为(1, 8)。
 * k=6  -->   mid(0) =left +fib[k-1]-1  mid(x) = min(mid(0) ,size-1)=7
 * 带入计算 (e==44) <==>E[index{x}]=75  e<E[index(x)}] 左区间
 * left (1)=left(0)=0  right(1)=mid(0)-1 =6 F(1)=F(0)-1 =5
 * 此时查找第二步为：同第一步，黄金分割点为第5个数字下标为4
 * mid(1) =left(1)+Fib(k-1)-1; = 0 + 5-1 =4
 */
class FibonacciSearch {


    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        int index = fibSearch(arr, 89);
        System.out.print("查找的下标为" + index);
    }

    //得到一个斐波那契数列
    private static int[] fib() {
        int maxSize = 20;
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    public static int fibSearch(int[] array, int findValue) {
        int low = 0;
        int high = array.length - 1;
        int[] f = fib();
        int mid = 0, k = 0;
        //得到斐波那契分割数值的下标k 比较斐波那契数列中的第k个元素大于目标数组的最后一个元素
        while (high > f[k] - 1) {
            k++;
        }
        //f[k] 可能大于array的长度,构造新的数组 并且指向temp 不足的位置不0 (原数组,新数组的长度f(k)=8)
        int[] temp = Arrays.copyOf(array, f[k]);
        for (int i = high + 1; i < temp.length; i++) {
            //用数组的最后一位去填充临时数组
            temp[i] = array[high];
        }
        while (low <= high) {
            mid = low + f[k - 1] - 1;
            if (findValue < temp[mid]) {
                high = mid - 1;
                k--;
            } else if (findValue > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}
